﻿#include <iostream>
#include <vector>

using namespace std;


/*
数字 n 代表生成括号的对数，请你设计一个函数，
用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]
 

提示：
1 <= n <= 8
*/






class Solution {
public:
	int left; int right;
	vector<string> ans;

	void dfs(string& s, int idx) {
		if (left + right == 0) {
			ans.push_back(s);
			return;
		}

		if (left !=0) {
			s.push_back('('); left--;
			dfs(s,idx+1);
			s.pop_back(); left++;
		}

		if (right > left && right != 0) {
			s.push_back(')'); right--;
			dfs(s, idx + 1);
			s.pop_back(); right++;
		}

		return;
	}

	vector<string> generateParenthesis(int n) {
		left = n; right = n;
		string s;
		dfs(s,0);

		return ans;
	}
};




//int main() {
//	Solution s;
//	s.generateParenthesis(3);
//
//	return 0;
//}